package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 20:50 2020/8/10
 * @Description
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PostorderTraversal {

    /*
     * 递归写法
     * */
  /*  List<Integer> ans = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        pre(root);
        return ans;
    }

    public void pre(TreeNode root) {
        if(root==null) return;
        pre(root.left);
        pre(root.right);
        ans.add(root.val);
    }

 */

    /**
     * 左右中->中右左->逆序
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        LinkedList<Integer> ansStack = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList();

        TreeNode p = root;

        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                ansStack.push(p.val);
                stack.add(p.left);
                p = p.right;
            }
            p = stack.pop();

        }

        while (!ansStack.isEmpty()) {
            ans.add(ansStack.pop());
        }
        return ans;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
